home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / flc2.arc / FLEXLIST.C < prev    next >
C/C++ Source or Header  |  1990-12-07  |  23KB  |  1,031 lines
  1. /*
  2.  
  3.     flexlist.c
  4.     10-4-90
  5.     Homogeneous-heterogeneous 
  6.     hybrid stack-queue-list-array generic class.
  7.     ANSI C
  8.  
  9.     Copyright 1990
  10.     John W. Small
  11.     All rights reserved
  12.  
  13.     PSW / Power SoftWare
  14.     P.O. Box 10072,
  15.     McLean, Virginia 22102 8072
  16.     (703) 759-3838
  17.  
  18. */
  19.  
  20.  
  21. #include <flexlist.h>    /*  <stddef.h>  size_t  */
  22. #include <stdlib.h>     /*  malloc(), free()  */
  23. #include <string.h>    /*  memcpy(), memset()  */
  24.  
  25.  
  26. /*  String variant FlexNode virtual functions  */
  27.  
  28. /*
  29.     FNnew() is called by FlexList functions (primitives)
  30.     that need to allocate new variant length FlexNodes,
  31.     e.g. FLpushD(), FLinsQD(), FLinsD(), FLinsSortD().
  32.     A pointer to the data to be placed in the new node
  33.     is passed to FNnew().  Your FNnew() function must
  34.     decide how large that data is and allocate a new 
  35.     FlexNode big enough to hold that data, i.e.
  36.  
  37.     FlexN N = malloc(sizeof(FlexNode) + 
  38.         sizeofYourData - 1).
  39.  
  40.     Your FNnew() function must also copy that data to
  41.     the new node.  "D" is never NULL!
  42.  
  43.     Please note that FNnew() could call a known function
  44.     pointer (function) in the data to determine its size.
  45.     It could also call another function to copy/
  46.     initialize the FlexNode data area from the data.
  47.     Data that contains its own functions for interfacing 
  48.     with itself are called objects.  Thus FlexLists can 
  49.     be made to hold polymorphic objects via the 
  50.     virtual function table functionology.
  51.  
  52.     Study all four virtual functions FNnew(), FNwrite(),
  53.     FNread(), and FNdestruct() for strings and how they
  54.     are called by the various FlexList functions to get
  55.     a better understanding of variant FlexLists.
  56. */
  57.  
  58. static FlexN FNnewStr(const void *D)
  59. {
  60.     FlexN N;
  61.     size_t i;
  62.  
  63.     for (i = 0; ((char *)D)[i++]; /* no reinit */)
  64.         /* null statement */;
  65.     if ((N = malloc(sizeof(FlexNode)+i-1)) != FlexN0)
  66.         (void) memcpy(N->data,D,i);
  67.     return N;
  68. }
  69.  
  70.  
  71. /*  FNwrite() is called by FLstoreD() to write variant data
  72.     to a variant FlexNode.  Make sure the new data 
  73.     doesn't write pass the end of the old.  FNwrite()
  74.     returns true if the write is successful.  "ND" and
  75.     "D" are never NULL! */
  76.  
  77. static int FNwriteStr(void *ND, const void *D)
  78. {
  79.     char *nd, *d;
  80.     
  81.     nd = (char *) ND;
  82.     d = (char *) D;
  83.     while (*nd)
  84.         if ((*nd++ = *d++) == '\0')
  85.             break;
  86.     return 1;
  87. }
  88.  
  89. /*  FNread() is called by FLtopD(), FLnextD(), 
  90.     FLprevD(), and FLrecallD() to read variant data
  91.     from a variant FlexNode.  FNread() returns true if
  92.     the read is successful.  "ND" and "D" are never 
  93.     NULL!  */
  94.  
  95. static int FNreadStr(const void *ND, void *D)
  96. {
  97.     char *nd, *d;
  98.     
  99.     nd = (char *) ND;
  100.     d = (char *) D;
  101.     while ((*d++ = *nd++) != '\0')
  102.         /* null statement */;
  103.     return 1;
  104. }
  105.  
  106. /*  FNdestruct() is called by FLclear(), FLdelete() via 
  107.     Flclear(), FLpopD(), and FLdelD() to destruct
  108.     variant data in a FlexNode.  Please note that
  109.     references to suballocated memory may be copied
  110.     to the outgoing data structure instead of being
  111.     cloned and then deallocated.  You must keep any
  112.     scheme straight though.  FLclear() always passes
  113.     NULL to the second parameter of FNdestruct() via
  114.     a call to FLpopD(L,0),    however, so any 
  115.     suballocated memory must be freed in that case!
  116.     "ND" is never NULL but "D" can be!  */
  117.  
  118. static int FNdestructStr(void *ND, void *D)
  119. {
  120.     char *nd, *d;
  121.     
  122.     nd = (char *)ND;
  123.     if ((d = (char *)D) != (char *)0) 
  124.         while ((*d++ = *nd++) != '\0')
  125.             /* null statement */;
  126.     return 1;
  127. }
  128.  
  129. /*  Any of the virtual functions can be absent.  The FlexList
  130.     functions that call them will simply return a failure
  131.     indication.  Use FNnew0, FNwrite0, FNread0, and/or
  132.     FNdestruct0 as zero initializers.  */
  133.  
  134. FlexNodeVFT FlexNodeStrVFT = { 
  135.     FNnewStr, FNwriteStr, FNreadStr, FNdestructStr };
  136.  
  137.  
  138. /*  FlexList constructors/destructor - static headers */
  139.  
  140.  
  141. #define FLzero(L) memset((void *)(L),0,sizeof(FlexList)-1)
  142.  
  143. FlexL FLfixed(FlexL L, size_t sizeofNodeData)
  144. {
  145.     if (!L)  
  146.         return L;
  147.     (void) FLzero(L);
  148.     if (!sizeofNodeData || sizeofNodeData 
  149.         > FLmaxSizeofNodeData)
  150.         return FlexL0;
  151.     L->maxNodes = FLmaxMaxNodes;
  152.     L->sizeofNodeData = sizeofNodeData;
  153.     L->sizeofNode = sizeof(FlexNode) 
  154.         + sizeofNodeData - 1;
  155.     L->sorted = 1;
  156.     return L;
  157. }
  158.  
  159. FlexL FLunpack(FlexL L, size_t sizeofCell, 
  160.     unsigned cells, const void *array)
  161. {
  162.     if (!L) 
  163.         return L;
  164.     (void) FLzero(L);
  165.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  166.         !sizeofCell || !cells || !array)
  167.         return FlexL0;
  168.     L->maxNodes = FLmaxMaxNodes;
  169.     L->sizeofNodeData = sizeofCell;
  170.     L->sizeofNode = sizeof(FlexNode) 
  171.         + sizeofCell - 1;
  172.     for (;cells && FLinsQD(L,array); cells--)
  173.         array = (char *) array + sizeofCell;
  174.     return L;
  175. }
  176.  
  177. FlexL FLvariant(FlexL L, FlexNVFT vft)
  178. {
  179.     if (!L)
  180.         return L;
  181.     (void) FLzero(L);
  182.     if (!vft)
  183.         return FlexL0;
  184.     L->maxNodes = FLmaxMaxNodes;
  185.     L->sorted = 1;
  186.     L->vft = vft;
  187.     return L;
  188. }
  189.  
  190. int   FLclear(FlexL L)
  191. {
  192.     while (FLpopD(L,(void *)0))
  193.         /* null statement */;
  194.     if (L) if (!L->nodes)
  195.         return (L->sorted = 1);
  196.     return 0;
  197. }
  198.  
  199. /*  FlexList constructors/destructor - dynamic headers  */
  200.  
  201. /*  FlexList headers are flagged as dynamic if and only if
  202.     FLDdestruct != NULL.  FLDmalloced() is the default
  203.     function pointer whenever one isn't specified.  */
  204. #pragma argsused
  205. /* ARGSUSED */ 
  206. static int FLDmalloced(void *LD)
  207. {    /*  LD is intentionally unused!  */
  208.     return 1;
  209. }
  210.  
  211. static FlexL FLnew(size_t sizeofLocalData, 
  212.     int (*FLDdestruct)(void *LD))
  213. {
  214.     FlexL L;
  215.  
  216.     if (sizeofLocalData > FLmaxSizeofLocalData) 
  217.         return FlexL0;
  218.     L = (FlexL) malloc(sizeof(FlexList) + 
  219.         sizeofLocalData - 1);
  220.     if (L)  {
  221.         (void) FLzero(L);
  222.         if (FLDdestruct)
  223.             L->FLDdestruct = FLDdestruct;
  224.         else
  225.             L->FLDdestruct = FLDmalloced;
  226.     }
  227.     return L;
  228. }
  229.  
  230. FlexL FLfixedNew(size_t sizeofNodeData,
  231.     size_t sizeofLocalData, 
  232.     int (*FLDdestruct)(void *LD))
  233. {
  234.     FlexL L;
  235.  
  236.     if (!sizeofNodeData || sizeofNodeData > 
  237.         FLmaxSizeofNodeData) 
  238.         return FlexL0;
  239.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  240.         != FlexL0)  {
  241.         L->maxNodes = FLmaxMaxNodes;
  242.         L->sizeofNodeData = sizeofNodeData;
  243.         L->sizeofNode = sizeof(FlexNode) 
  244.             + sizeofNodeData - 1;
  245.         L->sorted = 1;
  246.     }
  247.     return L;
  248. }
  249.  
  250. FlexL FLunpackNew(size_t sizeofCell, 
  251.     unsigned cells, const void *array,
  252.     size_t sizeofLocalData,
  253.     int (*FLDdestruct)(void *LD))
  254. {
  255.     FlexL L;
  256.  
  257.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  258.         !sizeofCell || !cells || !array)
  259.         return FlexL0;
  260.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  261.         != FlexL0)  {
  262.         L->maxNodes = FLmaxMaxNodes;
  263.         L->sizeofNodeData = sizeofCell;
  264.         L->sizeofNode = sizeof(FlexNode) 
  265.             + sizeofCell - 1;
  266.         for (;cells && FLinsQD(L,array); cells--)
  267.             array = (char *) array + sizeofCell;
  268.     }
  269.     return L;
  270. }
  271.  
  272. FlexL FLvariantNew(FlexNVFT vft,
  273.     size_t sizeofLocalData,
  274.     int (*FLDdestruct)(void *LD))
  275. {
  276.     FlexL L;
  277.  
  278.     if (!vft) 
  279.         return FlexL0;
  280.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  281.         != FlexL0)  {
  282.         L->maxNodes = FLmaxMaxNodes;
  283.         L->sorted = 1;
  284.         L->vft = vft;
  285.     }
  286.     return L;
  287. }
  288.  
  289. int FLdelete(FlexL *Lptr)
  290. {
  291.     if (!Lptr) 
  292.         return 0;
  293.     if (!(*Lptr)->FLDdestruct) 
  294.         return 0;
  295.     if (!(*((*Lptr)->FLDdestruct))((*Lptr)->data))
  296.         return 0;
  297.     if (!FLclear(*Lptr)) 
  298.         return 0;
  299.     free(*Lptr); 
  300.     *Lptr = FlexL0;
  301.     return 1;
  302. }
  303.  
  304.  
  305. /*  FlexList header functions  */
  306.  
  307. int FLsetMaxNodes(FlexL L, unsigned maxNodes)
  308. {
  309.     if (L)
  310.         if (maxNodes >= L->nodes)  {
  311.             L->maxNodes = maxNodes;
  312.             return 1;
  313.         }
  314.     return 0;
  315. }
  316.  
  317. int FLsetCompare(FlexL L, int (*compare)
  318.     (const void *D1, const void *D2))
  319. {
  320.     if (L)  {
  321.         L->compare = compare;
  322.         L->sorted = 0;
  323.         return 1;
  324.     }
  325.     return 0;
  326. }
  327.  
  328.  
  329. /*  FlexList stack and queue functions  */
  330.  
  331. void * FLpushN(FlexL L, FlexN N)
  332. {
  333.     if (!L || !N) 
  334.         return (void *) 0;
  335.     if (L->nodes >= L->maxNodes)  
  336.         return (void *) 0;
  337.     N->prev = FlexN0;
  338.     if ((N->next = L->front) != FlexN0)
  339.         N->next->prev = N;
  340.     else
  341.         L->rear = N;
  342.     L->front = N;
  343.     L->nodes++;
  344.     if (L->curNum) 
  345.         L->curNum++;
  346.     L->sorted = 0;
  347.     return N->data;
  348. }
  349.  
  350. void * FLpushD(FlexL L, const void *D)
  351. {
  352.     FlexN N;
  353.  
  354.     if (!L) 
  355.         return (void *) 0;
  356.     if (L->nodes >= L->maxNodes) 
  357.         return (void *) 0;
  358.     if (L->sizeofNode) {  /*  fixed size FlexNodes  */
  359.         if ((N = malloc(L->sizeofNode)) == FlexN0)
  360.             return (void *) 0;
  361.         if (D) 
  362.             memcpy(N->data,D,L->sizeofNodeData);
  363.         else
  364.             memset(N->data,0,L->sizeofNodeData);
  365.     }
  366.     else if (!L->vft || !D)
  367.         return (void *) 0;
  368.     else if (!L->vft->FNnew)
  369.         return (void *) 0;
  370.     else if ((N = (*L->vft->FNnew)(D)) == FlexN0)
  371.         return (void *) 0;
  372.     N->prev = FlexN0;
  373.     if ((N->next = L->front) != FlexN0)
  374.         N->next->prev = N;
  375.     else
  376.         L->rear = N;
  377.     L->front = N;      
  378.     L->nodes++;
  379.     if (L->curNum) 
  380.         L->curNum++;
  381.     L->sorted = 0;
  382.     return N->data;
  383. }
  384.  
  385. FlexN  FLpopN(FlexL L)
  386. {
  387.     FlexN N;
  388.     
  389.     if (!L) 
  390.         return FlexN0;
  391.     if ((N = L->front) == FlexN0)
  392.         return FlexN0;
  393.     if (L->front == L->rear)
  394.         L->rear = FlexN0;
  395.     else
  396.         N->next->prev = FlexN0;
  397.     L->front = N->next;
  398.     L->nodes--;
  399.     if (L->curNum)  
  400.         if (!--L->curNum)
  401.             L->current = FlexN0;
  402.     N->next = N->prev = FlexN0;
  403.     return N;
  404. }
  405.  
  406. int FLpopD(FlexL L, void *D)
  407. {
  408.     FlexN N;
  409.     
  410.     if (!L) 
  411.         return 0;
  412.     if ((N = L->front) == FlexN0)
  413.         return 0;
  414.     if (L->sizeofNodeData)  {
  415.         if (D)
  416.             memcpy(D,N->data,L->sizeofNodeData);
  417.     }
  418.     else if (!L->vft)
  419.         return 0;
  420.     else if (!L->vft->FNdestruct)
  421.         return 0;
  422.     else if (!(*L->vft->FNdestruct)(N->data,D))
  423.         return 0;
  424.     if (L->front == L->rear)
  425.         L->rear = FlexN0;
  426.     else
  427.         N->next->prev = FlexN0;
  428.     L->front = N->next;
  429.     L->nodes--;
  430.     if (L->curNum)  
  431.         if (!--L->curNum)
  432.             L->current = FlexN0;
  433.     free(N);
  434.     return 1;
  435. }
  436.  
  437. void * FLtopD(FlexL L, void *D)
  438. {
  439.     if (!L) 
  440.         return (void *) 0;
  441.     if (!L->front) 
  442.         return (void *) 0;
  443.     if (D) if (L->sizeofNodeData)
  444.         memcpy(D,L->front->data,L->sizeofNodeData);
  445.     else if (!L->vft)
  446.         return (void *) 0;
  447.     else if (!L->vft->FNread)
  448.         return (void *) 0;
  449.     else if (!(*L->vft->FNread)(L->front->data,D))
  450.         return (void *) 0;
  451.     return L->front->data;
  452. }
  453.  
  454. void * FLinsQN(FlexL L, FlexN N)
  455. {
  456.     if (!L || !N) 
  457.         return (void *) 0;
  458.     if (L->nodes >= L->maxNodes) 
  459.         return (void *) 0;
  460.     N->next = FlexN0;
  461.     if (L->rear)
  462.         L->rear->next = N;
  463.     else
  464.         L->front = N;
  465.     N->prev = L->rear;
  466.     L->rear = N;
  467.     L->nodes++;
  468.     L->sorted = 0;
  469.     return N->data;
  470. }
  471.  
  472. void * FLinsQD(FlexL L, const void *D)
  473. {
  474.     FlexN N;
  475.  
  476.     if (!L) 
  477.         return (void *) 0;
  478.     if (L->nodes >= L->maxNodes) 
  479.         return (void *) 0;
  480.     if (L->sizeofNode) {  /*  fixed size FlexNodes  */
  481.         if ((N = malloc(L->sizeofNode)) == FlexN0)
  482.             return (void *) 0;
  483.         if (D) 
  484.             memcpy(N->data,D,L->sizeofNodeData);
  485.         else
  486.             memset(N->data,0,L->sizeofNodeData);
  487.     }
  488.     else if (!L->vft || !D)
  489.         return (void *) 0;
  490.     else if (!L->vft->FNnew)
  491.         return (void *) 0;
  492.     else if ((N = (*L->vft->FNnew)(D)) == FlexN0)
  493.         return (void *) 0;
  494.     N->next = FlexN0;
  495.     if (L->rear)
  496.         L->rear->next = N;
  497.     else
  498.         L->front = N;
  499.     N->prev = L->rear;
  500.     L->rear = N;
  501.     L->nodes++;
  502.     L->sorted = 0;
  503.     return N->data;
  504. }
  505.  
  506. void * FLmkcur(FlexL L, unsigned n)
  507. {
  508.   if (!L) return (void *) 0;
  509.   if (!n || (n > L->nodes))  {  /*  out of range  */
  510.     L->current = 0;
  511.     L->curNum = 0;
  512.     return (void *) 0;
  513.   }
  514.   else if (n == L->curNum)  /*  already there  */
  515.     return L->current->data;
  516.   if (L->current)  /*  divide list into two parts  */
  517.     if (n > L->curNum)  /*  in last half of list  */
  518.       if (((L->nodes >> 1) + (L->curNum >> 1)) < n)
  519.     /*  rear closest */
  520.     for (L->current = L->rear, L->curNum = L->nodes;
  521.       L->curNum > n; L->curNum--)
  522.       L->current = L->current->prev;
  523.       else  /*  current closest  */
  524.     for (;L->curNum < n; L->curNum++)
  525.       L->current = L->current->next;
  526.     else  /* in first half of list  */
  527.       if ((L->curNum >> 1) < n)  /*  current closest  */
  528.     for (;L->curNum > n; L->curNum--)
  529.       L->current = L->current->prev;
  530.       else  /*  front closest  */
  531.     for (L->current = L->front, L->curNum = 1;
  532.       L->curNum < n; L->curNum++)
  533.       L->current = L->current->next;
  534.   else  /*  consider whole list  */
  535.     if ((L->nodes >> 1) < n)  /*  closer to rear  */
  536.       for (L->current = L->rear, L->curNum = L->nodes; 
  537.     L->curNum > n; L->curNum--)
  538.     L->current = L->current->prev;
  539.     else  /*  closer to front  */
  540.       for (L->current = L->front, L->curNum = 1;
  541.     L->curNum < n; L->curNum++)
  542.     L->current = L->current->next;
  543.   return L->current->data;
  544. }
  545.  
  546. void * FLinsN(FlexL L, FlexN N)
  547. {
  548.     if (!L || !N) 
  549.         return (void *) 0;
  550.     if (L->nodes >= L->maxNodes)
  551.         return (void *) 0;
  552.     if ((N->prev = L->current) == FlexN0)  {
  553.         if ((N->next = L->front) == FlexN0)
  554.             L->rear = N;
  555.         else
  556.             N->next->prev = N;
  557.         L->front = N;
  558.     }
  559.     else  {  /*  after current  */
  560.         if ((N->next = L->current->next) == FlexN0)
  561.             L->rear = N;  /*  last node  */
  562.         else 
  563.             N->next->prev = N;
  564.         L->current->next = N;
  565.     }
  566.     L->current = N;
  567.     L->curNum++;
  568.     L->nodes++;
  569.     L->sorted = 0;
  570.     return N->data;
  571. }
  572.  
  573. void * FLinsD(FlexL L, const void *D)
  574. {
  575.     FlexN N;
  576.  
  577.     if (!L) 
  578.         return (void *) 0;
  579.     if (L->nodes >= L->maxNodes) 
  580.         return (void *) 0;
  581.     if (L->sizeofNode) {  /*  fixed size FlexNodes  */
  582.         if ((N = malloc(L->sizeofNode)) == FlexN0)
  583.             return (void *) 0;
  584.         if (D) 
  585.             memcpy(N->data,D,L->sizeofNodeData);
  586.         else
  587.             memset(N->data,0,L->sizeofNodeData);
  588.     }
  589.     else if (!L->vft || !D)
  590.         return (void *) 0;
  591.     else if (!L->vft->FNnew)
  592.         return (void *) 0;
  593.     else if ((N = (*L->vft->FNnew)(D)) == FlexN0)
  594.         return (void *) 0;
  595.     if ((N->prev = L->current) == FlexN0)  {
  596.         if ((N->next = L->front) == FlexN0)
  597.             L->rear = N;
  598.         else
  599.             N->next->prev = N;
  600.         L->front = N;
  601.     }
  602.     else  {  /*  after current  */
  603.         if ((N->next = L->current->next) == FlexN0)
  604.             L->rear = N;  /*  last node  */
  605.         else 
  606.             N->next->prev = N;
  607.         L->current->next = N;
  608.     }
  609.     L->current = N;
  610.     L->curNum++;
  611.     L->nodes++;
  612.     L->sorted = 0;
  613.     return N->data;
  614. }
  615.  
  616. void * FLinsSortN(FlexL L, FlexN N)
  617. {
  618.     unsigned long low, high;
  619.     void *ok;
  620.  
  621.     if (!L || !N) 
  622.         return (void *) 0;
  623.     if (L->nodes >= L->maxNodes || !L->compare)
  624.         return (void *) 0;
  625.     if (!L->sorted)
  626.         (void) FLsort(L,FLcompare0);
  627.     low = 1UL;
  628.     high = (unsigned long) L->nodes;
  629.     while (low <= high)  
  630.         if ((*L->compare)(FLmkcur(L,
  631.             (unsigned)((low+high) >> 1)),
  632.             N->data) <= 0)
  633.             low = (unsigned long)
  634.                 (L->curNum + 1);
  635.         else
  636.             high = (unsigned long)
  637.                 (L->curNum - 1);
  638.     (void) FLmkcur(L,(unsigned)high);
  639.     ok = FLinsN(L,N);
  640.     L->sorted = 1;
  641.     return ok;
  642. }
  643.  
  644. void * FLinsSortD(FlexL L, const void *D)
  645. {
  646.     FlexN N;
  647.     unsigned long low, high;
  648.     void *ok;
  649.  
  650.     if (!L || !D) 
  651.         return (void *) 0;
  652.     if (L->nodes >= L->maxNodes || !L->compare) 
  653.         return (void *) 0;
  654.     if (L->sizeofNode) {  /*  fixed size FlexNodes  */
  655.         if ((N = malloc(L->sizeofNode)) == FlexN0)
  656.             return (void *) 0;
  657.         memcpy(N->data,D,L->sizeofNodeData);
  658.     }
  659.     else if (!L->vft)
  660.         return (void *) 0;
  661.     else if (!L->vft->FNnew)
  662.         return (void *) 0;
  663.     else if ((N = (*L->vft->FNnew)(D)) == FlexN0)
  664.         return (void *) 0;
  665.     if (!L->sorted)
  666.         (void) FLsort(L,FLcompare0);
  667.     low = 1UL;
  668.     high = (unsigned long) L->nodes;
  669.     while (low <= high)  
  670.         if ((*L->compare)(FLmkcur(L,
  671.             (unsigned)((low+high) >> 1)),
  672.             N->data) <= 0)
  673.             low = (unsigned long)
  674.                 (L->curNum + 1);
  675.         else
  676.             high = (unsigned long)
  677.                 (L->curNum - 1);
  678.     (void) FLmkcur(L,(unsigned)high);
  679.     ok = FLinsN(L,N);
  680.     L->sorted = 1;
  681.     return ok;
  682. }
  683.  
  684. FlexN  FLdelN(FlexL L)
  685. {
  686.     FlexN N;
  687.  
  688.     if (!L) 
  689.         return FlexN0;
  690.     if ((N = L->current) == FlexN0)
  691.         return FlexN0;
  692.     L->current = N->prev;
  693.     L->curNum--;
  694.     if (N->next)
  695.         N->next->prev = N->prev;
  696.     else
  697.         L->rear = N->prev;
  698.     if (N->prev)
  699.         N->prev->next = N->next;
  700.     else
  701.         L->front = N->next;
  702.     L->nodes--;
  703.     N->next = N->prev = FlexN0;
  704.     return N;
  705. }
  706.  
  707. int FLdelD(FlexL L, void *D)
  708. {
  709.     FlexN N;
  710.  
  711.     if (!L) 
  712.         return 0;
  713.     if ((N = L->current) == FlexN0)
  714.         return 0;
  715.     if (L->sizeofNodeData)  {
  716.         if (D) 
  717.             memcpy(D,N->data,L->sizeofNodeData);
  718.     }
  719.     else if (!L->vft)
  720.         return 0;
  721.     else if (!L->vft->FNdestruct)
  722.         return 0;
  723.     else if (!(*L->vft->FNdestruct)(N->data,D))
  724.         return 0;
  725.     L->current = N->prev;
  726.     L->curNum--;
  727.     if (N->next)
  728.         N->next->prev = N->prev;
  729.     else
  730.         L->rear = N->prev;
  731.     if (N->prev)
  732.         N->prev->next = N->next;
  733.     else
  734.         L->front = N->next;
  735.     L->nodes--;
  736.     free(N);
  737.     return 1;
  738. }
  739.  
  740. void * FLnextD(FlexL L, void *D)
  741. {
  742.     FlexN oldCurrent;
  743.  
  744.     if (!L) 
  745.         return (void *) 0;
  746.     if ((oldCurrent = L->current) != FlexN0)
  747.         L->current = L->current->next;
  748.     else
  749.         L->current = L->front;
  750.     if (!L->current) {
  751.         L->curNum = 0;
  752.         return (void *) 0;
  753.     }
  754.     if (D) if (L->sizeofNodeData) 
  755.         memcpy(D,L->current->data,
  756.             L->sizeofNodeData);
  757.     else if (!L->vft) {
  758.         L->current = oldCurrent;
  759.         return (void *) 0;
  760.     }
  761.     else if (!L->vft->FNread)  {
  762.         L->current = oldCurrent;
  763.         return (void *) 0;
  764.     }
  765.     else if (!(*L->vft->FNread)(L->current->data,D))  {
  766.         L->current = oldCurrent;
  767.         return (void *) 0;
  768.     }
  769.     L->curNum++;
  770.     return L->current->data;
  771. }
  772.  
  773. void * FLprevD(FlexL L, void *D)
  774. {
  775.     FlexN oldCurrent;
  776.     unsigned oldCurNum;
  777.  
  778.     if (!L) 
  779.         return (void *) 0;
  780.     oldCurNum = L->curNum;
  781.     if ((oldCurrent = L->current) != FlexN0)  {
  782.         L->current = L->current->prev;
  783.         L->curNum--;
  784.     }
  785.     else  {
  786.         L->current = L->rear;
  787.         L->curNum = L->nodes;
  788.     }
  789.     if (!L->current)
  790.         return (void *) 0;
  791.     if (D) if (L->sizeofNodeData) 
  792.         memcpy(D,L->current->data,
  793.             L->sizeofNodeData);
  794.     else if (!L->vft)  {
  795.         L->curNum = oldCurNum;
  796.         L->current = oldCurrent;
  797.         return (void *) 0;
  798.     }
  799.     else if (!L->vft->FNread)  {
  800.         L->curNum = oldCurNum;
  801.         L->current = oldCurrent;
  802.         return (void *) 0;
  803.     }
  804.     else if (!(*L->vft->FNread)(L->current->data,D))  {
  805.         L->curNum = oldCurNum;
  806.         L->current = oldCurrent;
  807.         return (void *) 0;
  808.     }
  809.     return L->current->data;
  810. }
  811.  
  812. void * FLfindFirstD(FlexL L, const void *D)
  813. {
  814.   unsigned long low, high;
  815.  
  816.   if (!L || !D) 
  817.     return (void *) 0;
  818.   if (!L->compare)
  819.     return (void *) 0;
  820.   if (L->sorted)  {
  821.     low = 1UL;
  822.     high = (unsigned long) L->nodes;
  823.     while (low <= high)  
  824.       if ((*L->compare)(FLmkcur(L,
  825.     (unsigned)((low+high) >> 1)),D) < 0)
  826.     low = (unsigned long) (L->curNum + 1);
  827.       else
  828.     high = (unsigned long) (L->curNum - 1);
  829.     if (FLmkcur(L,(unsigned)high+1))
  830.       if (!(*L->compare)(L->current->data,D))
  831.     return L->current->data;
  832.     /*  leave at insertion point  */
  833.     (void) FLmkcur(L,(unsigned)high);
  834.   }
  835.   else  {
  836.     (void) FLmkcur(L,0);
  837.     while (FLnextD(L,(void *)0))
  838.       if (!(*L->compare)(L->current->data,D))
  839.     return L->current->data;  
  840.   }
  841.   return (void *) 0;
  842. }
  843.  
  844. void * FLfindNextD(FlexL L, const void *D)
  845. {
  846.     if (!L || !D) 
  847.         return (void *) 0;
  848.     if (!L->compare)
  849.         return (void *) 0;
  850.     while (FLnextD(L,(void *)0))
  851.         if (!(*L->compare)(L->current->data,D))
  852.             return L->current->data;  
  853.         else if (L->sorted)
  854.             break;
  855.     return (void *) 0;
  856. }
  857.  
  858. void * FLfindLastD(FlexL L, const void *D)
  859. {
  860.   unsigned long low, high;
  861.  
  862.   if (!L || !D) 
  863.     return (void *) 0;
  864.   if (!L->compare)
  865.     return (void *) 0;
  866.   if (L->sorted)  {
  867.     low = 1UL;
  868.     high = (unsigned long) L->nodes;
  869.     while (low <= high)  
  870.       if ((*L->compare)(FLmkcur(L,
  871.     (unsigned)((low+high) >> 1)),D) <= 0)
  872.     low = (unsigned long) (L->curNum + 1);
  873.       else
  874.     high = (unsigned long) (L->curNum - 1);
  875.     if (FLmkcur(L,(unsigned)high))
  876.       if (!(*L->compare)(L->current->data,D))
  877.     return L->current->data;
  878.   }
  879.   else  {
  880.     (void) FLmkcur(L,0);
  881.     while (FLprevD(L,(void *)0))
  882.       if (!(*L->compare)(L->current->data,D))
  883.     return L->current->data;  
  884.   }
  885.   return (void *) 0;
  886. }
  887.  
  888. void * FLfindPrevD(FlexL L, const void *D)
  889. {
  890.     if (!L || !D) 
  891.         return (void *) 0;
  892.     if (!L->compare)
  893.         return (void *) 0;
  894.     while (FLprevD(L,(void *)0))
  895.         if (!(*L->compare)(L->current->data,D))
  896.             return L->current->data;  
  897.         else if (L->sorted)
  898.             break;
  899.     return (void *) 0;
  900. }
  901.  
  902. int   FLsort(FlexL L, int (*compare)
  903.     (const void *D1, const void *D2))
  904. {
  905.     FlexList tmp;
  906.  
  907.     if (!L) 
  908.         return 0;
  909.     if (L->sorted)  {
  910.         if (L->compare == compare || !compare)
  911.             { FLmkcur(L,0); return 1; }
  912.     }
  913.     else if (!L->compare && !compare) 
  914.         return 0;
  915.     if (compare)
  916.         L->compare = compare;
  917.     if (!L->nodes)
  918.         return (L->sorted = 1);
  919.     (void) FLzero(&tmp);
  920.     tmp.maxNodes = FLmaxMaxNodes;
  921.     tmp.sorted = 1;
  922.     tmp.compare = L->compare;
  923.     while (L->nodes)
  924.         (void) FLinsSortN(&tmp,FLpopN(L));
  925.     L->front = tmp.front;
  926.     L->rear = tmp.rear;
  927.     L->nodes = tmp.nodes;
  928.     return (L->sorted = 1);
  929. }
  930.  
  931. int FLstoreD(FlexL L, const void *D, unsigned n)
  932. {
  933.     unsigned oldn;
  934.  
  935.     if (!L || !D) 
  936.         return 0;
  937.     if (n > L->nodes || !n && !L->current)
  938.         return 0;
  939.     if (L->sizeofNodeData)  {
  940.         if (n) (void) FLmkcur(L,n);
  941.         memcpy(L->current->data,D,
  942.             L->sizeofNodeData);
  943.     }
  944.     else if (!L->vft)
  945.         return 0;
  946.     else if (!L->vft->FNwrite)
  947.         return 0;
  948.     else  {
  949.         oldn = L->curNum;
  950.         if (n) (void) FLmkcur(L,n);
  951.         if (!(*L->vft->FNwrite)(L->current->data,D))
  952.         {
  953.             (void) FLmkcur(L,oldn);
  954.             return 0;
  955.         }
  956.     }
  957.     L->sorted = 0;
  958.     return 1;
  959. }
  960.  
  961. int FLrecallD(FlexL L, void *D, unsigned n)
  962. {
  963.     unsigned oldn;
  964.  
  965.     if (!L || !D) 
  966.         return 0;
  967.     if (n > L->nodes || !n && !L->current)
  968.         return 0;
  969.     if (L->sizeofNodeData)  {
  970.         if (n) (void) FLmkcur(L,n);
  971.         memcpy(D,L->current->data,
  972.             L->sizeofNodeData);
  973.     }
  974.     else if (!L->vft)
  975.         return 0;
  976.     else if (!L->vft->FNread)
  977.         return 0;
  978.     else  {
  979.         oldn = L->curNum;
  980.         if (n) (void) FLmkcur(L,n);
  981.         if (!(*L->vft->FNread)(L->current->data,D))
  982.         {
  983.             (void) FLmkcur(L,oldn);
  984.             return 0;
  985.         }
  986.     }
  987.     return 1;
  988. }
  989.  
  990. void * FLpack(FlexL L)  /*  Only fixed nodes!  */
  991. {
  992.     long sizeofArray;
  993.     char *A, *Ai;
  994.     FlexN N;
  995.  
  996.     if (!L) return (void *) 0;
  997.     sizeofArray = ((long)L->sizeofNodeData)
  998.         * ((long)L->nodes);
  999.     if ((sizeofArray <= 0) || 
  1000.         (sizeofArray > FLmaxSizeofArray))
  1001.         return (void *) 0;
  1002.     if ((A = malloc((unsigned) sizeofArray)) 
  1003.         == (char *) 0)
  1004.         return (void *) 0;
  1005.     for (Ai = A, N = L->front; N; N = N->next,
  1006.         Ai += L->sizeofNodeData)
  1007.         memcpy(Ai,N->data,L->sizeofNodeData);
  1008.     return A;
  1009. }
  1010.  
  1011. void **FLpackPtrs(FlexL L)
  1012. {
  1013.     long sizeofArray;
  1014.     void **A;
  1015.     unsigned Ai;
  1016.     FlexN N;
  1017.  
  1018.     if (!L) return (void **) 0;
  1019.     sizeofArray = sizeof(void *) * ((long)L->nodes + 1);
  1020.     if ((sizeofArray <= 0) ||
  1021.         (sizeofArray > FLmaxSizeofArray))
  1022.         return (void **) 0;
  1023.     if ((A = malloc((unsigned) sizeofArray)) 
  1024.         == (void **) 0)
  1025.         return (void **) 0;
  1026.     for (Ai = 0, N = L->front; N; Ai++, N = N->next)
  1027.         A[Ai] = N->data; 
  1028.     A[Ai] = (void *) 0;
  1029.     return A;
  1030. }
  1031.